package cn.zifangsky.array;

import org.junit.Test;

/**
 * 二分法查找一个有序数组
 *
 * @author zifangsky
 * @date 2020/10/21
 * @since 1.0.0
 */
public class BinarySearch {
    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int[] arr1 = new int[]{0, 1, 2, 4, 5, 6, 7};
        int[] arr2 = new int[]{1, 2, 3, 4, 5};
        int[] arr3 = new int[]{1};

        //结果：4
        System.out.println(this.search(arr1, 5));
        //结果：-1
        System.out.println(this.search(arr1, 3));
        //结果：2
        System.out.println(this.search(arr2, 3));
        //结果：1
        System.out.println(this.search(arr2, 2));
        //结果：0
        System.out.println(this.search(arr3, 1));
        //结果：-1
        System.out.println(this.search(arr3, 0));
    }

    /**
     * 二分查找一个有序数组
     *
     * @param nums 给定的有序数组
     * @param target 目标值
     * @return int 目标值在数组中的索引，如果不存在就返回-1
     */
    public int search(int[] nums, int target) {
        if(nums == null || nums.length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        int left = 0, right = nums.length - 1;
        while (left <= right){
            int mid = (right + left) / 2;

            if(nums[mid] == target){
                return mid;
            }
            if(nums[left] == target){
                return left;
            }
            if(nums[right] == target){
                return right;
            }

            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        return -1;
    }

}
